package com.lw.leetcode.arr.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 2271. 毯子覆盖的最多白色砖块数
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/15 21:41
 */
public class MaximumWhiteTiles {


    public static void main(String[] args) {
        MaximumWhiteTiles test = new MaximumWhiteTiles();

        // 9
        int[][] tiles = {{1, 5}, {10, 11}, {12, 18}, {20, 25}, {30, 32}};
        int carpetLen = 10;

        // 2
//        int[][] tiles = {{10,11},{1,1}};
//        int carpetLen = 2;


        int i = test.maximumWhiteTiles(tiles, carpetLen);
        System.out.println(i);
    }

    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {

        Arrays.sort(tiles, (a, b) -> Integer.compare(a[0], b[0]));

        int length = tiles.length;
        int len = 1;
        for (int i = 1; i < length; i++) {
            if (tiles[i][0] == tiles[i - 1][1] + 1) {
                tiles[i][0] = tiles[i - 1][0];
                tiles[i - 1][1] = -1;
                tiles[i - 1][0] = -1;
            } else {
                len++;
            }
        }
        len <<= 1;
        int[] as = new int[len];
        int[] bs = new int[len];
        int j = 0;
        for (int[] tile : tiles) {
            if (tile[0] != -1) {
                int index = j << 1;
                as[index] = tile[0];
                bs[index] = 1;
                as[index + 1] = tile[1] + 1;
                bs[index + 1] = 0;
                j++;
            }
        }
        long sum = 0;
        int st = as[0];
        int end = st + carpetLen;
        int i = 1;
        for (; i < len; i++) {
            if (as[i] < end) {
                sum += (as[i] - as[i - 1]) * bs[i - 1];
            } else {
                sum += (end - as[i - 1]) * bs[i - 1];
                break;
            }
        }
        if (i == len) {
            return (int) sum;
        }
        int left = 1;
        int right = i;
        long max = sum;
        while (right < len) {
            int lc = as[left] - st;
            int rc = as[right] - end;
            if (lc == rc) {
                st += lc;
                end += lc;
                sum -= lc * bs[left - 1];
                sum += lc * bs[right - 1];
                left++;
                right++;
            } else if (lc < rc) {
                st += lc;
                end += lc;
                sum -= lc * bs[left - 1];
                sum += lc * bs[right - 1];
                left++;
            } else {
                st += rc;
                end += rc;
                sum -= rc * bs[left - 1];
                sum += rc * bs[right - 1];
                right++;
            }
            max = Math.max(max, sum);
        }
        return (int) max;
    }

}
